package org.ala.linshen.dp;

import java.math.BigInteger;
import java.util.*;

/**
 * 给你一个整数数组 rewardValues，长度为 n，代表奖励的值。
 *
 * 最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：
 *
 * 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
 * 如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。
 * 以整数形式返回执行最优操作能够获得的 最大 总奖励。
 *
 *
 *
 * 示例 1：
 *
 * 输入：rewardValues = [1,1,3,3]
 *
 * 输出：4
 *
 * 解释：
 *
 * 依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。
 *
 * 示例 2：
 *
 * 输入：rewardValues = [1,6,4,3,2]
 *
 * 输出：11
 *
 * 解释：
 *
 * 依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。
 *
 *
 *
 * 提示：
 *
 * 1 <= rewardValues.length <= 2000
 * 1 <= rewardValues[i] <= 2000
 *
 * @author ala
 * @date 2024-10-08 09:41
 */
public class Q3180 {

    public static void main(String[] args) {
        Q3180 q = new Q3180();

//        int[] rewardValues = {1,1,3,3};
//        int[] rewardValues = {1,6,4,3,2};
        int[] rewardValues = {5,9,6,15};

        System.out.println(q.maxTotalReward(rewardValues));
    }

    public int maxTotalReward(int[] rewardValues) {
//        return V1(rewardValues);
        return V2(rewardValues);
    }
    /**
     *  1）dp[i][j]表示前i个数（含i）能否到达j
     *  2）第i个数有选或不选：
     *      不选：dp[i][j] = dp[i - 1][j]
     *      选：  dp[i][j] = dp[i - 1][j - v]   j - v >= 0 并且 v > j - v
     *      dp[i][j] = dp[i - 1][j] 或者 dp[i - 1][j - v]
     *  3）dp[i][0] = true
     *      j 最大到 max(rewardValues) * 2
     *  4）dp[N][j] == true 的最大的j就是答案
     */
    protected int V1(int[] rvs) {
        Set<Integer> set = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        int mx = 0;
        for (int n : rvs) {
            if (set.add(n)) {
                list.add(n);
                mx = Math.max(mx, n);
            }
        }
        if (set.contains(mx - 1)) {
            return 2 * mx - 1;
        }

        list.sort((i1, i2) -> i1 - i2);
        int N = list.size();
        mx = list.get(N - 1) << 1;

        boolean[] dp = new boolean[mx + 1];
        dp[0] = true;
        for (int i = 1 ; i <= N ; i++) {
            int v = list.get(i - 1);
            for (int j = mx ; j >= v ; j--) {
                if (j >= v && j < (v << 1)) {
                    dp[j] |= dp[j - v];
                }
            }
        }
        for (int j = mx ; j >= 0 ; j--) {
            if (dp[j]) {return j;}
        }
        return -1;
    }
    protected int V2(int[] rvs) {
        Set<Integer> set = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        int mx = 0;
        for (int n : rvs) {
            if (set.add(n)) {
                list.add(n);
                mx = Math.max(mx, n);
            }
        }
        if (set.contains(mx - 1)) {
            return 2 * mx - 1;
        }

        list.sort((i1, i2) -> i1 - i2);
        int N = list.size();

        BigInteger bi = BigInteger.ONE;
        set = new HashSet<>();
        for (int n : list) {
            if (set.contains(mx - 1 - n)) {
                return 2 * mx - 1;
            }
            set.add(n);

            BigInteger mark = bi.and(BigInteger.ONE.shiftLeft(n).subtract(BigInteger.ONE));
            bi = bi.or(mark.shiftLeft(n));
        }
        return bi.bitLength() - 1;
    }
}
